package com.剑指Offer;

/*
 * 
 * 替换空格
 * 请实现一个函数，把字符串中的每个空格替换成“%20”
 * 考虑算法的时间复杂度
 */

public class 题4替换字符串空格 {

	//利用jdk提供的函数直接替换
	public static String process1(String string) {
		if (string == null || string.length() == 0) {
			return null;
		}
		String xixi = string.replaceAll(" ", "%20");
		return xixi;
	}

	//下面的方法时间复杂度为O(n平方)
	//涉及到数组中元素的移动
	public static char[] process2(char[] string) {
		if (string == null || string.length == 0) {
			return null;
		}
		int length = 0;
		for (int i = 0; i < string.length; i += length) {
			if (string[i] == ' ') {
				char[] hehe = string;
				string = new char[string.length + 2];
				System.arraycopy(hehe, 0, string, 0, hehe.length);
				for (int j = hehe.length - 1; j >= i + 1; j--) {
					string[j + 2] = string[j];
				}
				string[i] = '%';
				string[i + 1] = '2';
				string[i + 2] = '0';
				length = 2;
				continue;
			}
			length = 1;
		}
		return string;
	}

	// 下面的方法时间复杂度为O(n)
	// 预先分配好空间，从新数组的尾部开始插入
	public static char[] process3(char[] string) {
		if (string == null || string.length == 0) {
			return null;
		}
		//先统计字符串中空格字符出现的次数
		int count = 0;
		for (int i = 0; i < string.length; i++) {
			if (string[i] == ' ') {
				count++;
			}
		}
		if (count == 0) {
			return string;
		}
		char[] hehe = string;
		//重新申请空间
		string = new char[string.length + 2 * count];
		System.arraycopy(hehe, 0, string, 0, hehe.length);

		//将两个指针指向字符数组的末尾
		int p2 = string.length - 1;
		int p1 = hehe.length - 1;
		//字符串替换操作
		while (p1 >= 0) {
			if (string[p1] == ' ') {
				string[p2--] = '0';
				string[p2--] = '2';
				string[p2--] = '%';
				p1--;
			} else {
				string[p2] = string[p1];
				p2--;
				p1--;
			}
		}
		return string;
	}

	public static void main(String[] args) {
		String xixi ="   ";
		char[] haha = xixi.toCharArray();
		System.out.println(process1(xixi));

		char[] hehe = process2(haha);
		if (hehe != null)
			System.out.println(hehe);
		else
			System.out.println("null");

		hehe = process3(haha);
		if (hehe != null)
			System.out.println(hehe);
		else
			System.out.println("null");
	}

}
